//
// Created by Senhai Xu on 2024/7/4.
//
#include <iostream>
#include<vector>
#include<queue>
#include <algorithm>
using namespace std;
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
//     构造函数（非默认）
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */


//根据节点值来获取路径 然后比较路径 最后一个不同点之前的为最近公共祖先
    vector<int> getPath(TreeNode * root,int target){
        vector<int> path = {};
        TreeNode* node = root;
        while(node->val!=target){
            path.emplace_back(node->val);
//            比节点值大 在右子树找
            if(target>node->val){
                node = node->right;
            }
            else{
                node = node->left;
            }
        }
        path.emplace_back(node->val);
        return path;

    }
    int lowestCommonAncestor(TreeNode* root, int p, int q) {
       vector<int> path1 = getPath(root,p);
       vector<int> path2 = getPath(root,q);
       int res = 0;
       for(int i = 0;i<path1.size()&&i<path2.size();i++){
           if(path1[i]==path2[i]){
               res =  path1[i];
           }
           else{
               break;
           }
       }
       return res;

    }


//方法二：二叉树递归
/*
step 1：首先检查空节点，空树没有公共祖先。
step 2：对于某个节点，比较与p、q的大小，若p、q在该节点两边说明这就是最近公共祖先。
step 3：如果p、q都在该节点的左边，则递归进入左子树。
step 4：如果p、q都在该节点的右边，则递归进入右子树。
 */
    int lowestCommonAncestor2(TreeNode* root, int p, int q) {
        if(root == NULL)
            return -1;
        if((p<=root->val&&q>=root->val)||(p>=root->val&&q<=root->val)){
            return root->val;
        }
        else if (p<root->val&&q<root->val){
            return lowestCommonAncestor2(root->left,p,q);
        } else {
            return lowestCommonAncestor2(root->right, p, q);
        }
    }

};